package hot100;

import java.util.ArrayList;
import java.util.List;

public class letterCombinations2 {
    String[] map = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    List<String> ret;
    StringBuffer path;
    int ori;
    public List<String> letterCombinations(String digits) {

        ret =  new ArrayList<>();
        path = new StringBuffer();
        if(digits.length() == 0) {
            return ret;
        }
        ori = 0;
        dfs(digits,ori);
        return ret;
    }

    void dfs(String digits,int index) {
        //组合长度满足
        if(path.length() == digits.length()) {
            ret.add(path.toString());
            return;
        }

        //确认 digits[index] 对应的map位置
        index = digits.charAt(ori) - '0';

        //开始组合字母
        for(int i = 0;i < map[index].length();i++) {
            path.append(map[index].charAt(i));
            ori++;
            dfs(digits,index + 1);
            path.deleteCharAt(path.length() - 1);
            ori--;
        }

    }
}
